package com.notes.algo.exam;

/**
 * @author
 * @Describe 转发模块的核心功能之一是根据功能号/接口名来进行路由转发。路由匹配的基本原理是判断实际请求中的功能号/接口名是否与预先配置的转发规则匹配，转发规则支持 '?' 和 '*' 通配符（'?'表示匹配任意单个字符；'*'表示匹配零个或多个任意字符）
 * @date
 */
public class Solution4 {
    public static void main(String[] args) {
        java.util.Scanner sc = new java.util.Scanner(java.lang.System.in);
        String matchStr = sc.next();
        String matchRule = sc.next();
        /*boolean isMatch = isMatch2(matchStr, matchRule);
        System.out.println(isMatch);*/
        boolean isMatch = isMatch3(matchStr, matchRule);
        System.out.println(isMatch);
    }

    public static boolean isMatch(String matchStr, String matchRule) {
        // 数据合规校验 。。。
        // TODO

        int k = 0;
        int sLength = matchStr.length();
        int ruleLength = matchRule.length();
        for (int i = 0; i < sLength; i++) {
            // 匹配字符串i位置值
            char curV = matchStr.charAt(i);
            for (int j = 0; j < ruleLength; j++) {
                char c = matchRule.charAt(j);
                if (c == '*') {
                    continue;
                }

                // 匹配上了 下一个字符比较
                if (c == '?' || c == curV) {
                    break;
                }

                if (curV != c) {
                    return false;
                }
            }
        }

        return k == ruleLength;
    }

    public static boolean isMatch2(String matchStr, String matchRule) {
        // 数据合规校验 。。。
        // TODO
        int i = 0;
        int j = 0;
        // 匹配*的位置
        int ss = -1;
        // *位置
        int rs = -1;
        while (i < matchStr.length()) {
            if (j < matchRule.length() && matchRule.charAt(j) == '*') {
                // 字符串的i位置匹配规则j位置的*通配符，匹配串往下查找非通配符*号位置
                ss = i;
                rs = j;
                j ++;
            } else if (j < matchRule.length() && (matchRule.charAt(j) == '?' || matchStr.charAt(i) == matchRule.charAt(j))) {
                // 通配符？和两个对应位置的字符相等情况为匹配，继续下一个字符匹配
                i ++;
                j ++;
            } else {
                // 没有通配符*匹配
                if (rs == -1) {
                    return false;
                }

                // 回到上一次通配符*位置
                j = rs;
                // 字符串从下一个进行匹配
                i = ss + 1;
            }
        }

        // 匹配串剩余的字符是否都是*
        while (j < matchRule.length() && matchRule.charAt(j) == '*') {
            j ++;
        }

        // 匹配串是否处理到最后
        return j == matchRule.length();
    }

    public static boolean isMatch3(String matchStr, String matchRule) {
        // 字符串长度
        int msl = matchStr.length();
        // 匹配规则长度
        int mrl = matchRule.length();
        // result[m][n]储存字符串前m个字符和匹配规则的前n个字符是否能匹配（true表示匹配false表示不匹配）
        // 数组中下标从0开始，所以构造的数组的长度需+1表示当前串的前n个子串
        boolean[][] result = new boolean[msl + 1][mrl +1];
        // 空串和空匹配是匹配
        result[0][0] = true;
        // 1.字符串为空是，若匹配串前面的字符都为*则为匹配，即为true
        for (int i = 1; i <= mrl; ++i) {
            if (matchRule.charAt(i - 1) == '*') {
                result[0][i] = true;
            } else {
                break;
            }
        }

        // 2.字符串不为空
        for (int i = 1; i <= msl; ++i) {
            for (int j = 1; j <= mrl; ++j) {
                if (matchRule.charAt(j - 1) == '*') {
                    // 通配符为*表示可以匹配0个或多个 此时比较字符串和匹配串的前一个或者下一个是否否匹配
                    result[i][j] = result[i][j -1] || result[i - 1][j];
                } else if (matchRule.charAt(j - 1) == '?' || matchStr.charAt(i - 1) == matchRule.charAt(j - 1)) {
                    // 当匹配符为？或者匹配符和字符串对应的位置相同时，则需要看下字符串和匹配串前一个的匹配是否能匹配
                    result[i][j] = result[i - 1][j - 1];
                }
            }
        }

        return result[msl][mrl];
    }
}
